package leetcode_day._2021._202105._2131;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/28 21:55
 * 汉明距离总和
 * 算法：位运算
 * 暴力解法 --- O(n * n)
 * 所有数字从高位到低位来
 * 看每一位可以有几个不同的
 * 找规律，每一位的不同数量 = 这个位上所有数的 1 的个数 × 0 的个数
 * O(32 * n)
 */
public class _28_477 {
    public static void main(String[] args) {
        System.out.println(new _28_477().totalHammingDistance(new int[]{4, 14, 2}));
    }

    public int totalHammingDistance(int[] nums) {
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            int a = 0, b = 0;
            for (int num : nums) {
                if ((num >> i & 1) == 0) ++a;
                else  ++b;
            }
            ans += a * b;
        }
        return ans;
    }

}
